#include <stdio.h>
#include <stdlib.h>

// 1. 双向链表节点结构定义
typedef struct DoubleLinkedListNode {
    int data;                          // 数据域
    struct DoubleLinkedListNode *prev; // 前驱指针（头节点prev=NULL）
    struct DoubleLinkedListNode *next; // 后继指针（尾节点next=NULL）
} DListNode, *PDListNode;

// 2. 初始化：非循环链表初始化（空表时头指针为NULL）
void DList_Init(PDListNode *head) {
    *head = NULL; // 空链表，头指针指向NULL
}

// 3. 创建新节点
PDListNode DList_CreateNode(int data) {
    PDListNode newNode = (PDListNode)malloc(sizeof(DListNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    newNode->data = data;
    newNode->prev = NULL; // 新节点默认前驱后继都为NULL
    newNode->next = NULL;
    return newNode;
}

// 4. 头插节点：在链表头部插入（新节点成为新头）
int DList_InsertHead(PDListNode *head, int data) {
    PDListNode newNode = DList_CreateNode(data);
    if (newNode == NULL) return 1;

    if (*head == NULL) { // 空表：新节点直接作为头节点
        *head = newNode;
    } else { // 非空表：新节点前驱为NULL，后继指向原头
        newNode->next = *head;
        (*head)->prev = newNode; // 原头节点前驱指向新节点
        *head = newNode;         // 更新头指针为新节点
    }
    return 0;
}

// 5. 尾插节点：在链表尾部插入（新节点成为新尾）
int DList_InsertTail(PDListNode *head, int data) {
    PDListNode newNode = DList_CreateNode(data);
    if (newNode == NULL) return 1;

    if (*head == NULL) { // 空表：新节点直接作为头节点（也是尾节点）
        *head = newNode;
    } else { // 非空表：先找到尾节点（next=NULL的节点）
        PDListNode tail = *head;
        while (tail->next != NULL) {
            tail = tail->next;
        }
        // 尾节点后继指向新节点，新节点前驱指向尾节点
        tail->next = newNode;
        newNode->prev = tail;
    }
    return 0;
}

// 6. 辅助函数：找到第pos个数据节点（pos从1开始，返回NULL表示越界）
static PDListNode DList_FindPosNode(PDListNode head, int pos) {
    if (head == NULL || pos < 1) return NULL;

    PDListNode curr = head;
    int count = 1;
    // 遍历到第pos个节点，或遇到NULL（节点数不足）
    while (curr != NULL && count < pos) {
        curr = curr->next;
        count++;
    }
    // 只有计数等于pos且节点非空，才返回该节点
    return (count == pos && curr != NULL) ? curr : NULL;
}

// 7. 指定位置插入：在第pos个数据节点后插入
int DList_InsertPos(PDListNode *head, int pos, int data) {
    // 特殊情况：pos=0等效头插（可选处理，此处按正常逻辑）
    if (pos == 0) {
        return DList_InsertHead(head, data);
    }

    // 找到第pos个节点
    PDListNode posNode = DList_FindPosNode(*head, pos);
    if (posNode == NULL) {
        printf("位置越界，插入失败\n");
        return 1;
    }

    PDListNode newNode = DList_CreateNode(data);
    if (newNode == NULL) return 1;

    newNode->prev = posNode;          // 新节点前驱 = 第pos个节点
    newNode->next = posNode->next;    // 新节点后继 = 第pos个节点的原后继
    if (posNode->next != NULL) {      // 若第pos个节点不是尾节点，需更新其原后继的前驱
        posNode->next->prev = newNode;
    }
    posNode->next = newNode;          // 第pos个节点后继 = 新节点
    return 0;
}

// 8. 删除所有值为target的节点
int DList_DeleteByValue(PDListNode *head, int target) {
    if (*head == NULL) return 1;

    PDListNode curr = *head;
    PDListNode temp;

    while (curr != NULL) {
        temp = curr;
        curr = curr->next; // 先移动指针，避免删除后无法访问下一个节点

        if (temp->data == target) {
            if (temp->prev == NULL) { // 待删节点是头节点
                *head = temp->next;   // 更新头指针为下一个节点
                if (*head != NULL) {  // 若新头非空，其前驱置为NULL
                    (*head)->prev = NULL;
                }
            } else if (temp->next == NULL) { // 待删节点是尾节点
                temp->prev->next = NULL;     // 前驱节点后继置为NULL
            } else { // 待删节点是中间节点
                temp->prev->next = temp->next;
                temp->next->prev = temp->prev;
            }
            free(temp); // 释放节点内存
        }
    }
    return 0;
}

// 9. 正向遍历：从车头到车尾（头节点→尾节点）
void DList_TraverseForward(PDListNode head) {
    if (head == NULL) {
        printf("正向遍历：链表为空\n");
        return;
    }

    PDListNode curr = head;
    printf("正向遍历：");
    while (curr != NULL) {
        printf("%d", curr->data);
        curr = curr->next;
        if (curr != NULL) printf(" <=> "); // 最后一个节点后不加箭头
    }
    printf("\n");
}

// 10. 反向遍历：从车尾到车头（尾节点→头节点）
void DList_TraverseBackward(PDListNode head) {
    if (head == NULL) {
        printf("反向遍历：链表为空\n");
        return;
    }

    // 先找到尾节点（next=NULL的节点）
    PDListNode tail = head;
    while (tail->next != NULL) {
        tail = tail->next;
    }

    // 从尾节点向前遍历（prev指针）
    PDListNode curr = tail;
    printf("反向遍历：");
    while (curr != NULL) {
        printf("%d", curr->data);
        curr = curr->prev;
        if (curr != NULL) printf(" <=> "); // 最后一个节点后不加箭头
    }
    printf("\n");
}

// 11. 销毁链表：释放所有节点，头指针置空
void DList_Destroy(PDListNode *head) {
    if (head == NULL || *head == NULL) return;

    PDListNode curr = *head;
    PDListNode temp;
    while (curr != NULL) {
        temp = curr;
        curr = curr->next; // 先移动指针
        free(temp);        // 释放当前节点
    }
    *head = NULL; // 头指针置空，避免野指针
}

// 12. 测试函数：验证非循环链表功能（插入1->2->3，反向遍历3->2->1）
int main() {
    PDListNode head;
    DList_Init(&head); // 初始化空链表

    // 尾插1→2→3（链表变为1<=>2<=>3，尾节点3的next=NULL）
    DList_InsertTail(&head, 1);
    DList_InsertTail(&head, 2);
    DList_InsertTail(&head, 3);

    // 测试遍历（核心验证点）
    DList_TraverseForward(head); // 预期：1 <=> 2 <=> 3
    DList_TraverseBackward(head); // 预期：3 <=> 2 <=> 1

    // （可选测试：删除、指定位置插入）
    // DList_DeleteByValue(&head, 2); // 删除值为2的节点，链表变为1<=>3
    // DList_InsertPos(&head, 1, 1.5); // 在第1个节点后插入1.5，链表变为1<=>1.5<=>3

    // 销毁链表（避免内存泄漏）
    DList_Destroy(&head);
    return 0;
}